//选择排序
// function selectionSort(arr) {
//    if (arr.length < 2) {
//        return arr
//    }
//     for (let i = 0; i < arr.length; i++) {
//        let min = i;
          //遍历i以后剩下的数据，获取最小值
//        for (let j = i; j < arr.length; j++) {
//            if (arr[j] < arr[min]) {
//               min = j;
//            }
//        }
          //将最小值跟i交换
//        if(min !== i) {
//            let temp = arr[min]
//            arr[min] = arr[i]
//            arr[i] = temp
//        }
//     }
//     return arr
// }

//冒泡排序
// function bubbleSort(arr) {
//    if (arr.length < 2) {
//        return arr
//    }
//     for (let i = 0; i < arr.length; i++) {
           //对未排序的数组继续冒泡
//         for (let j = 0; j < arr.length - i - 1; j++) {
//            if (arr[j] > arr[j + 1]) {
//                let temp = arr[j]
//                arr[j] = arr[j + 1]
//                arr[j + 1] = temp
//            }
//         }
//     }
//     return arr
// }

//插入排序
// function insertSort(arr) {
//    if (arr.length < 2) {
//        return arr
//    }
//     for (let i = 1; i < arr.length; i++) {
//         let index = i - 1 
//         value = arr[i]
            //在0到i范围内从右向左遍历寻找第一个比valu小的值
//         while(value < arr[index] && index >= 0) {
//             arr[index + 1] = arr[index]
//             index--
//         }
           //将上一个大于value的值替换为value
//         arr[index + 1] = value
//     }
//     return arr
// }

//归并排序
// function mergeSort(arr) {
//     if (arr.length < 2) {
//         return arr;
//     }
//     let method = []
//     let mid = Math.floor(arr.length / 2)
//     let left = arr.splice(0, mid)
//     let arr1 = mergeSort(left)
//     let arr2 = mergeSort(arr)
        //将两个有序数组合并
//     while(arr1.length && arr2.length) {
//         if (arr1[0] >= arr2[0]) {
//             method.push(arr2.shift())
//         } else {
//             method.push(arr1.shift())
//         }
//     }
//     return [...method,...arr1,...arr2]
// }

//快速排序
//  function quickSort(arr) {
//      if (arr.length < 2) {
//          return arr
//      }
//      let left = []
//      let right = []
//      let min = Math.floor(arr.length / 2)
        //将基数提取出来处理边界问题
//      let value = arr.splice(min,1)[0];
//      for (let i = 0;i < arr.length;i++) {
//          if (arr[i] < value) {
//              left.push(arr[i])
//          } else {
//              right.push(arr[i])
//          }
//      }
//      left = quickSort(left)
//      right = quickSort(right)
//      return [...left,value,...right]
//  }

//堆排序
function heapSort(arr) {
   function maxHeap(arr, start, end) {
       let parent = start
       let son = parent*2 + 1
       while (son <= end) {
           if(son + 1 <= end && arr[son] < arr[son + 1]) son++
           if (arr[son] > arr[parent]) {
               let temp = arr[son]
                arr[son] = arr[parent]
                arr[parent] = temp
                parent = son;
                son = parent*2 + 1;
           } else {
               return
           }
       }
   }
   for (let i = Math.ceil(arr.length/2 - 1);i >= 0; i--) {
       maxHeap(arr,i,arr.length - 1)
   }

   for (let i = arr.length - 1;i > 0;i--) {
       let temp = arr[0]
       arr[0] = arr[i]
       arr[i] = temp
       maxHeap(arr,0,i-1)
   }
   return arr
}

const arr = [5, 4, 3, 2, 1];
console.log(heapSort(arr));